package 题目集.图.最短路;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/minimum-cost-to-reach-destination-in-time/?envType=daily-question&envId=2024-10-03
 */
public class demo03_改点为边的dij {

    /**
     * dijkstra
     * 这题其实是可以跑dj的，把to点的权值看作是from到to的代价。
     * 题目原边的权值对跑dj没有意义，只是提供了一个跑dj的限制，即此条dj路线的边之和必须小于指定值。
     * 所以思路为：先将点权值转化为第二类边，在根据第二类边跑dj,跑的过程中看看第一类边的和时候小于指定值
     *
     * @param maxTime
     * @param edges
     * @param passingFees
     * @return
     */
    static int maxn = 1010;
    List<int[]>[] graph = new List[maxn];
    int[] passingFees;

    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        this.passingFees = passingFees;
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int t = edge[2];
            graph[u].add(new int[]{v, t, passingFees[v]});    /*0位置to点、1：第一类边，2：第二类边*/
            graph[v].add(new int[]{u, t, passingFees[u]});    /*0位置to点、1：第一类边，2：第二类边*/
        }
        return dijkstra(0, maxTime);
    }

    public int dijkstra(int s, int limit) {
        int[] dis2 = new int[passingFees.length];
        int[] dis1 = new int[passingFees.length];
        Arrays.fill(dis2, Integer.MAX_VALUE);
        Arrays.fill(dis1, Integer.MAX_VALUE);
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        queue.add(new int[]{s, 0, passingFees[0]}); /*起点到该点第一类边和第二类边的值*/
        dis1[s] = 0;
        dis2[s] = passingFees[0];
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int u = curr[0];
            int d1 = curr[1];
            int d2 = curr[2];
            /*抵达终点*/
            if (u == passingFees.length - 1) return d2;
            for (int[] e : graph[u]) {
                int v = e[0];
                int newD1 = d1 + e[1];
                int newD2 = d2 + e[2];
                /*当前点抵达to点超时*/
                if (newD1 > limit) continue;
                if (newD2 < dis2[v]) {
                    /*
                    * 如果存在比之前更短的路，那么之前的d1没有意义。
                    * 因为d1是在最短路超限制的情况下的第二手选择，如果最短路没有超限制，那么d1没意义。
                    * 所以这里可以直接替换掉d1
                    */
                    dis1[v] = newD1;
                    dis2[v] = newD2;
                    queue.add(new int[]{v,newD1,newD2});
                } else if (newD1 < dis1[v]) {
                    dis1[v] = newD1;
                    queue.add(new int[]{v,newD1,newD2});
                }
            }
        }
        return -1;
    }

}
